1. Field of the Invention
The present invention relates to data processing systems, and more particularly to data processing systems having plural processing elements running simultaneously, each having a capability of producing branch condition signals asynchronously.
2. Prior Art
High performance data processing systems typically include several processing elements which perform computations under program control. An example of a processing element is a fixed point arithmetic and logic unit ("ALU") which performs arithmetic and logical operations on integer data. Another example of a processing element is a floating point ALU which performs arithmetic and logical operations on floating point data. Each processing element customarily produces condition signals which indicate conditions relevant to results being produced by the processing element. The signals may be interrogated by a subsequent conditional branch instruction and a decision made to branch or not to branch. A field of data bits which specify how the condition signals produced by a processing element are to be interpreted is referred to as a predicate field. A predicate field is usually part of the branch instruction. That is, it is an immediate field contained in the instruction or it is implied by the operation code of the branch instruction. Some computer architectures, such as the IBM ESA/390 architecture, generally described in ESA/390 Principles of Operation, IBM Publication No. SA22-7201-00 (1992), require that the condition signals of all processing elements in an implementation be reduced to a single condition code which may then be interrogated by a branch on condition instruction. The data processing system is required to reduce the condition signals of all processing elements into a single condition code. This reduction is complicated in a high performance system by the presence of many processing elements, differing instruction processing latencies between the processing elements, and for superscaler or for very long instruction word ("VLIW") systems, managing multiple condition signals being produced concurrently.
Reduction of condition signals from multiple processing elements to a single condition code necessarily discards potentially useful information, namely, the condition signals from the processing elements other than the one which was allowed to set the condition code. The IBM RISC System/6000 Architecture, as described in Assembler Language Reference for AIX Version 0.3 for RISC System/6000, IBM Publication No. 8C23-2197 (1992), alleviates this problem somewhat by defining separate fixed point and floating point condition register fields. The fixed point condition register field is set exclusively by fixed point processing element condition signals. The floating point condition register field is set exclusively by floating point process element condition signals. However, in a system with, for example, multiple fixed point ALUs, only one fixed point ALU is permitted to set the fixed point ALU condition register field in a given processor cycle. The condition signals from the other fixed point ALUs are lost.
By contrast, VLIW architectures typically define multiple condition codes, condition register fields, or some analogous structure. "A Wide Instruction Word Architecture for Parallel Execution of Logic Programs Coded in BSL" by Ebcioglu and Kumar, published in New Generation Computing, Volume 7, pp. 219-242 (1990), refers to condition codes CC0 through CCn-1 in a VLIW processor having n processors. To branch on n condition codes, however, requires n branch instructions, which although they may be executed in parallel, expend considerable instruction memory space and instruction bandwidth. Further, because of the tree like structure of a VLIW instruction, evaluation of CCj will preclude the evaluation of CCk (j not equal to k) if a branch on CCj redirects the instruction stream. It is, therefore, not possible to evaluate complex logical combinations of condition codes with a single branch instruction, for example "branch if ((CC0 and CC1) or CC2).
An article by Colwell, et at., entitled "A VLIW Architecture for a Trace Scheduling Compiler" published in IEEE Transactions on Computers, Vol. 37, No. 8, August, 1988, pp. 967-979 defines a 7 bit "branch bank" each bit of which is equivalent to a single bit condition code. Compare instructions are the only instructions which may set branch bank bits and a given compare instruction must specify which bit in the branch bank is to be set. Up to 7 compare instructions executing in parallel can each set its own branch bank bit, provided that the instructions were coded accordingly. However, as with the Ebcioglu, et al. reference, to branch on n branch bank bits requires n branch instructions, which expends considerable instruction memory space and instruction bus bandwidth. Further, a multiway branch in the Colwell, et al., machine is in essence a prioritized decision tree. Thus, the evaluation of branch bank bit j will preclude the evaluation of branch bank bit k (j not equal to k) if a branch on branch bank bit j redirects the instruction stream. It is, therefore, not possible to evaluate complex combination of branch bank bits with a single branch instruction.
An article by Emma, et al. entitled "Multiple Queued Condition Codes" published in the IBM Technical Disclosure Bulletin, Vol. 31, No. 2, July, 1988 at pp. 294-296 describes a technique which provides a queue of condition codes ("CC") which may be set by CC-setting instructions (for example, compare instructions) in a first in, first out register ("FIFO"), and thus sequential manner. Instructions that test CCs (for example, branch instructions) may test any CC in the queue, but also in a sequential manner. The article indicates that VLIW processors can test the CCs in parallel, but no mechanism is described.
By contrast, the data processing system according to the present invention allows multiple CCs to be set in parallel (that is, there is no FIFO restriction), includes a mechanism for testing multiple CCs in parallel, and permits multiple CCs to be combined in boolean expressions to formulate single cycle complex tests, thereby reducing or eliminating the need for sequences of branch instructions, which would require multiple processor cycles.
U.S. Pat. No. 5,093,908 to Beacom, et al. describes a data processing system including a synchronization mechanism between a main processor and a tightly coupled co-processor. The main processor is allowed to run ahead of the co-processor in the instruction stream, that is execute instruction sequentially ahead of the instruction being executed by the co-processor. The synchronization mechanism assures that sequential program behavior is preserved and that interrupts are reported precisely. It appears that the synchronization mechanism forces sequential execution when instructions executing in both the main and the co-processor attempt to set the condition code. The synchronization mechanism detects all conditions which might be violated by the co-processor before it has finished performing an instruction and holds off the main processor from executing a subsequent instruction.
In contrast, the data processing system according to the present invention requires no synchronization since each processor produces its own condition code. The synchronization mechanism in the Beacom et al. patent forces sequential program execution, thereby decreasing processor throughput whenever synchronization is necessary. Further, the data processing system according to the present invention allows multiple condition codes to be combined into complex boolean expressions, a concept which is not suggested by the patent.